package array;

import java.util.Stack;

/**
 * 42. 接雨水
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
 * 计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * <p>
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 */
public class Problem_42 {
    public static void main(String[] args) {

        System.out.println(new Problem_42().trap_1(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(new Problem_42().trap_2(new int[]{4, 2, 0, 3, 2, 5}));
        System.out.println(new Problem_42().trap_3(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));


    }

    /**
     * 方法一：动态规划
     * 对于下标 i，下雨后水能到达的最大高度等于下标 i 左右两边的最大高度中的最小值，
     * 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]
     *
     * @param height
     * @return
     */
    public int trap_1(int[] height) {
        int result = 0;
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        for (int i = 0; i < height.length - 1; i++) {
            result += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return result;
    }

    /**
     * 方法二：单调栈
     * 维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
     *
     * @param height
     * @return
     */
    public int trap_2(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for (int i = 0; i < height.length; i++) {
            // 如果 当前位置i处的高度 大于 栈顶位置处的高度，则表示左边可以形成积水的低洼
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop(); //取出栈顶元素，即积水处的下标位置
                if (stack.isEmpty()) {
                    break;
                }
                int distance = i - stack.peek() - 1;//横向距离，即积水的宽度
                result += distance * (Math.min(height[i], height[stack.peek()]) - height[top]);
            }

            stack.push(i);
        }

        return result;
    }

    /**
     * 方法三：双指针
     * 在方法一的动态规划做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。
     * 是否可以将空间复杂度降到 O(1)？
     * 由于下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。
     * 而数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，
     * 因此可以使用双指针和两个变量代替两个数组。
     *
     * @param height
     * @return
     */
    public int trap_3(int[] height) {
        int result = 0;

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                // 如果左边 有了更高值
                if (height[left] > leftMax) {
                    leftMax = height[left];
                }
                // 表示能够积水
                else {
                    result += leftMax - height[left];
                }
                left++;

            } else {
                if (height[right] > rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }

        }

        return result;
    }

}
